package edu.washington.cs.workflow.matching;

import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import com.ibm.wala.classLoader.IMethod;
import com.ibm.wala.ipa.callgraph.CGNode;
import com.ibm.wala.ipa.callgraph.CallGraph;

import edu.washington.cs.workflow.analysis.AnalysisBuilder;
import edu.washington.cs.workflow.util.Utils;
import edu.washington.cs.workflow.util.WALAUtils;

public class ExecutionTraceMatcher {

	public final AnalysisBuilder oldBuilder;
	public final AnalysisBuilder newBuilder;
	
	private CallGraph oldcg = null;
	private CallGraph newcg = null;
	
	public ExecutionTraceMatcher(AnalysisBuilder oldBuilder,
			AnalysisBuilder newBuilder) {
		Utils.checkNotNull(oldBuilder);
		Utils.checkNotNull(newBuilder);
		this.oldBuilder = oldBuilder;
		this.newBuilder = newBuilder;
		//init the new/old cg
		this.oldcg = this.oldBuilder.getCallGraph();
		this.newcg = this.newBuilder.getCallGraph();
	}
	
	/**
	 * Find all counterpart
	 * */
	public String findCounterpartSig(String oldSig) {
		CGNode matchedNode = this.findCounterpart(oldSig);
		if(matchedNode == null) {
			return null;
		}
		return matchedNode.getMethod().getSignature();
	}
	public CGNode findCounterpart(String oldSig) {
		CGNode oldNode = WALAUtils.lookupCGNode(oldcg, oldSig);
		if(oldNode == null) {
			Utils.debugPrintln("Cannot find method: " + oldSig);
			return null;
		}
		Utils.checkNotNull(oldNode, oldSig);
		return findCounterpart(oldNode);
	}
	public CGNode findCounterpart(CGNode oldNode) {
		//exact match by name
		CGNode exactMatched = this.findMatchedMethodByName(oldNode);
		if(exactMatched != null) {
			return exactMatched;
		}
		//same classname + methodname, without the package names
		CGNode sameNode = this.findSameMethodByName(oldNode);
		if(sameNode != null) {
			return sameNode;
		}
		//use name similarity
		Collection<CGNode> methods = this.findAllSimilarMethodsByFullName(oldNode);
		if(!methods.isEmpty()) {
			return methods.iterator().next();
		}
		
		return null;
	}
	
	public CGNode findMostSimilarMethodByFullName(CGNode oldNode) {
		Collection<CGNode> methods = this.findAllSimilarMethodsByFullName(oldNode);
		if(!methods.isEmpty()) {
			return methods.iterator().next();
		}
		
		return null;
	}
	
	/**
	 * Only compare the name
	 * */
	public String findMostSimilarMethodSigByMethodName(String methodSignature) {
		CGNode oldNode = WALAUtils.lookupCGNode(this.oldcg, methodSignature);
		if(oldNode == null) {
			Utils.debugPrintln("No node found for: " + methodSignature);
			return null;
		}
		CGNode matchedNode = findMostSimilarMethodByMethodName(oldNode);
		if(matchedNode == null) {
			Utils.debugPrintln("No matched node for: " + methodSignature);
			return null;
		}
		return matchedNode.getMethod().getSignature();
	}
	
	public CGNode findMostSimilarMethodByMethodName(CGNode oldNode) {
		Collection<CGNode> methods = this.findAllSimilarMethodsByMethodName(oldNode);
		if(!methods.isEmpty()) {
			return methods.iterator().next();
		}
		
		return null;
	}
	
	@Deprecated
	public CGNode findMatchedMethodByNameSig(String methodSignature) {
		CGNode oldNode = WALAUtils.lookupCGNode(this.oldcg, methodSignature);
		Utils.checkNotNull(oldNode, "Not exist: " + methodSignature);
		return this.findMatchedMethodByName(oldNode);
	}
	
	//XXX a very naive approach, to find the same method
	CGNode findMatchedMethodByName(CGNode oldNode) {
		for(CGNode newNode : this.newcg) {
			if(isExactMatched(newNode, oldNode)) {
				return newNode;
			}
		}
		return null;
	}
	
	/**
	 * Compare the qualified name
	 * */
	Collection<CGNode> findAllExactMatchedMethodsByName(CGNode oldNode) {
		Collection<CGNode> coll = new LinkedList<CGNode>();
		for(CGNode newNode : this.newcg) {
			if(isExactMatched(newNode, oldNode)) {
				coll.add(newNode);
			}
		}
		return coll;
	}
	
	/**
	 * Just compare class + method name, without any package names. Also,
	 * discard the inner class signature
	 * */
	/**Just return the first matched one*/
	CGNode findSameMethodByName(CGNode oldNode) {
		for(CGNode newNode : this.newcg) {
			if(isMethodNameMatched(newNode, oldNode)) {
				return newNode;
			}
		}
		return null;
	}
	/**Return all matched ones*/
	Collection<CGNode> findAllSameMethodsByName(CGNode oldNode) {
		Collection<CGNode> coll = new LinkedList<CGNode>();
		for(CGNode newNode : this.newcg) {
			if(isMethodNameMatched(newNode, oldNode)) {
				coll.add(newNode);
			}
		}
		return coll;
	}
	
	/**
	 * Such as: net.sourceforge.ganttproject.gui.scrolling.ScrollingManagerImpl.scrollBy
	 *      v.s. net.sourceforge.ganttproject.gui.scrolling.ScrollingManagerImpl.scrollRight
	 * */
	private boolean verbose = false;
	private int default_num = 5;
	private float default_threshold = 0.0f;
	public void setSimilarNumber(int num) {
		Utils.checkTrue(num > 0);
		this.default_num = num;
	}
	public void setThreshold(float thres) {
		Utils.checkTrue(thres > 0.0f);
		this.default_threshold = thres;
	}
	Collection<CGNode> findAllSimilarMethodsByFullName(CGNode oldNode) {
		String[] newAppPkgName = this.newBuilder.appPackages;
		String methodSig = oldNode.getMethod().getSignature();
		String methodName = WALAUtils.getFullMethodName(oldNode.getMethod());
		Map<CGNode, Float> nodeMap = new LinkedHashMap<CGNode, Float>();
		for(CGNode newNode : this.newcg) {
			String newMethodSig = newNode.getMethod().getSignature();
			if(!Utils.startWith(newMethodSig, newAppPkgName)) {
				continue; //only compare app methods
			}
			//only check method name, without the argument values
//			Float similarity = Utils.computeLevenshteinSimilarity(methodSig, newNode.getMethod().getSignature());
			Float similarity = Utils.computeLevenshteinSimilarity(methodName, WALAUtils.getFullMethodName(newNode.getMethod()));
			nodeMap.put(newNode, similarity);
		}
		nodeMap = Utils.sortByValue(nodeMap, false);
		Collection<CGNode> similarMethods = new LinkedList<CGNode>();
		Iterator<CGNode> it = nodeMap.keySet().iterator();
		while(similarMethods.size() < default_num && it.hasNext()) {
			CGNode method = it.next();
			float score = nodeMap.get(method);
			if(score > this.default_threshold) {
			    similarMethods.add(method);
			}
			if(verbose) {
			    System.err.println(" method: " + method + ", score: " + nodeMap.get(method));
			}
		}
		
		return similarMethods;
	}
	
	//just compare class.method name(args)
	Collection<CGNode> findAllSimilarMethodsByMethodName(CGNode oldNode) {
		String[] newAppPkgName = this.newBuilder.appPackages;
		String fullMethodName = WALAUtils.getFullMethodName(oldNode.getMethod());
		String pkgName = WALAUtils.getJavaPackageName(oldNode.getMethod().getDeclaringClass());
		String methodName = fullMethodName.substring(pkgName.length() + 1 /*skip dot*/);
		if(methodName.indexOf("$") != -1) {
			methodName = methodName.substring(methodName.indexOf("$") + 1);
		}
		Map<CGNode, Float> nodeMap = new LinkedHashMap<CGNode, Float>();
		for(CGNode newNode : this.newcg) {
			String newMethodSig = newNode.getMethod().getSignature();
			if(!Utils.startWith(newMethodSig, newAppPkgName)) {
				continue; //only compare app methods
			}
			String newFullMethodName = WALAUtils.getFullMethodName(newNode.getMethod());
			if(fullMethodName.equals(newFullMethodName)) {
				continue; //skip identical ones
			}
			String newPackageName = WALAUtils.getJavaPackageName(newNode.getMethod().getDeclaringClass());
			String newMethodName = newFullMethodName.substring(newPackageName.length() + 1);
			if(newMethodName.indexOf("$") != -1) {
				newMethodName = newMethodName.substring(newMethodName.indexOf("$") + 1);
			}
			//only check method name, without the argument values
//			Float similarity = Utils.computeLevenshteinSimilarity(methodSig, newNode.getMethod().getSignature());
			Float similarity = Utils.computeLevenshteinSimilarity(methodName, newMethodName);
			nodeMap.put(newNode, similarity);
		}
		nodeMap = Utils.sortByValue(nodeMap, false);
		Collection<CGNode> similarMethods = new LinkedList<CGNode>();
		Iterator<CGNode> it = nodeMap.keySet().iterator();
		while(similarMethods.size() < default_num && it.hasNext()) {
			CGNode method = it.next();
			float score = nodeMap.get(method);
			if(score > this.default_threshold) {
			    similarMethods.add(method);
			}
			if(verbose) {
			    System.err.println(" method: " + method + ", score: " + nodeMap.get(method));
			}
		}
		
		return similarMethods;
	}
	
	private boolean isExactMatched(CGNode node1, CGNode node2) {
		if(node1.getMethod().getSignature().equals(node2.getMethod().getSignature())) {
			return true;
		}
		return false;
	}
	
	/** discard the package name, if it is an internal class. discard the
	    outside class name.
	    e.g., 
	         net.sourceforge.ganttproject.action.ZoomInAction.actionPerformed
	    v.s. net.sourceforge.ganttproject.action.zoom.ZoomInAction.actionPerformed
	    
	         freemind.controller.MapModuleManager.nextMapModule()V
	    v.s. freemind.controller.Controller$MapModuleManager.nextMapModule()V
	    */
	private boolean isMethodNameMatched(CGNode node1, CGNode node2) {
		IMethod method1 = node1.getMethod();
		IMethod method2 = node2.getMethod();
		
		String sig1 = method1.getSignature();
		String pkgName1 = WALAUtils.getJavaPackageName(method1.getDeclaringClass());
		Utils.checkTrue(sig1.startsWith(pkgName1));
		String methodName1 = sig1.substring(pkgName1.length() + 1 /**remove the dot*/);
		
		String sig2 = method2.getSignature();
		String pkgName2 = WALAUtils.getJavaPackageName(method2.getDeclaringClass());
		Utils.checkTrue(sig2.startsWith(pkgName2));
		String methodName2 = sig2.substring(pkgName2.length() + 1 /**remove the dot*/);
		
//		if(node2.getMethod().getSignature().indexOf("MapModuleManager.nextMapModule()V") != -1) {
//			System.out.println(" ==== " + methodName1);
//			System.out.println("     ==== " + methodName2);
//		}
		
		if(methodName1.equals(methodName2)) {
			return true;
		}
		
		if(methodName1.endsWith(methodName2) || methodName2.endsWith(methodName1)) {
			return true;
		}
		
		return false;
	}
	
	/**
	 * Implements a variant of Martin Robillard's ICSE08 paper, by reversing the call
	 * relations.
	 * 
	 * similarity(m1, m2) = calles(m1) union calles(m2) / calles (m2)
	 * 
	 * Here m2 is the new method which can be a candidate
	 * 
	 * XXX What about a major refactoring? move to different refactoring. how to match
	 * the method. What about method split?
	 * 
	 * */
	@Deprecated
	public Map<CGNode, Float> findMatchedMethodByCallRelation(CGNode oldNode) {
		
		//get transitive call closure.
		List<CGNode> oldReachableNodes = WALAUtils.getReachableAppNodesOneLevel(oldNode, this.oldcg, this.oldBuilder.appPackages);
		oldReachableNodes.remove(oldNode);
		
		System.out.println("-- old reachable nodes: ");
		for(CGNode oldN : oldReachableNodes) {
			System.out.println(oldN.getMethod().getSignature());
		}
		
		
		
//		Collection<CGNode> newNodes = SwingHelper.getEventHandlingMethods(this.newcg,
//				this.newBuilder.getClassHierarchy(), this.newBuilder.appPackages);
//		
//		Collection<CGNode> newNodes = this.newBuilder.getCallGraph()
		
		Map<CGNode, Float> nodeScores = new LinkedHashMap<CGNode, Float>();
		for(CGNode newNode : this.newBuilder.getCallGraph()) {
			//skip nodes which does not belong to the app
			String pkg = WALAUtils.getJavaPackageName(newNode.getMethod().getDeclaringClass());
			if(!Utils.startWith(pkg, newBuilder.appPackages)) {
				continue;
			}
			
			System.out.println("Analyzing node: " + newNode);
			
			Collection<CGNode> newReachableNodes = WALAUtils.getReachableAppNodesOneLevel(newNode,
					this.newcg, this.newBuilder.appPackages);
			newReachableNodes.remove(newNode);
			Float similarity = this.computeSimilarityViaCalls(oldReachableNodes, newReachableNodes);
			if(!similarity.equals(Float.NaN)) {
			    nodeScores.put(newNode, similarity);
			    
				System.out.println("    old reachble nodes: " + oldReachableNodes.size()
						+ ", new reachable nodes: " + newReachableNodes.size());
				System.out.println("    similarity score: " + similarity);
				for(CGNode oldN : newReachableNodes) {
					System.out.println("       "  + oldN.getMethod().getSignature());
				}
			}
			
			//reclaim memory
			newReachableNodes.clear();
		}
		
		Map<CGNode, Float> sortedMap = Utils.sortByValue(nodeScores, false);
		
		return sortedMap;
	}
	
	/**
	 * 
	 * similarity(m1, m2) = calles(m1) union calles(m2) / calles (m2)
	 * 
	 * Here m2 is the new method which can be a candidate*/
	@Deprecated
	private Float computeSimilarityViaCalls(Collection<CGNode> oldNodes, Collection<CGNode> newNodes) {
		Collection<CGNode> sharedNodes = intersect(oldNodes, newNodes);
		return (float)sharedNodes.size() / //(float) oldNodes.size(); 
		    (float)(Math.max(newNodes.size(), oldNodes.size())); //newNodes.size();
	}
	
	/**
	 * The intersection of 2 collections. The element is only from the old node set.
	 * */
	@Deprecated
	private Collection<CGNode> intersect(Collection<CGNode> oldNodes, Collection<CGNode> newNodes) {
		Collection<CGNode> sharedNodes = new LinkedHashSet<CGNode>();
		for(CGNode oldNode : oldNodes) {
			boolean shared = false;
			for(CGNode newNode : newNodes) {
				if(sameNode(oldNode, newNode)) {
					shared = true;
					break;
				}
			}
			if(shared) {
				sharedNodes.add(oldNode);
			}
		}
		return sharedNodes;
	}
	
	/**
	 * Nodes from both collections
	 * */
	@Deprecated
    private Collection<CGNode> union(Collection<CGNode> oldNodes, Collection<CGNode> newNodes) {
    	Collection<CGNode> unionNodes = new LinkedHashSet<CGNode>();
		for(CGNode oldNode : oldNodes) {
			boolean shared = false;
			for(CGNode newNode : newNodes) {
				if(sameNode(oldNode, newNode)) {
					shared = true;
					break;
				}
			}
			if(!shared) {
				unionNodes.add(oldNode);
			}
		}
		unionNodes.addAll(newNodes);
		return unionNodes;
	}
	
	private boolean sameNode(CGNode oldNode, CGNode newNode) {
		String oldMethodWithoutArgs = WALAUtils.getJavaFullClassName(oldNode.getMethod().getDeclaringClass())
		 + "." + oldNode.getMethod().getName().toString();
		String newMethodWithoutArgs = WALAUtils.getJavaFullClassName(newNode.getMethod().getDeclaringClass())
		 + "." + newNode.getMethod().getName().toString();
		return oldMethodWithoutArgs.equals(newMethodWithoutArgs);
	}
}